package algorithm.swordoff;

/**
 * 序列化二叉树
 */

public class SQ37 {

    StringBuilder sb = new StringBuilder();
    String[] split;
    int index = 0;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        serializeHelper(root);
        sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }

    /**
     * 本质是一个前序遍历
     * @param node
     */
    private void serializeHelper(TreeNode node) {
        if (node == null) {
            sb.append("N").append("#");
            return;
        }

        sb.append(node.val).append("#");
        serializeHelper(node.left);
        serializeHelper(node.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        split = data.split("#");
        return deserializeHelper();

    }

    /**
     * 仍然是前序遍历,注意这个index++,其实当前index指向的字符串可能是N也可能不是N,是一个if-else关系
     * 在if-else分别执行的时候index指向的是同一个,而在if里面处理完了要++,处理完else也要++
     * @return
     */
    private TreeNode deserializeHelper() {
        if (split[index].equals("N")) {
            index++;
            return null;
        }

        TreeNode curr = new TreeNode(Integer.parseInt(split[index++]));
        curr.left = deserializeHelper();
        curr.right = deserializeHelper();
        return curr;
    }

}